package algoGenetic;

import java.util.*;
import java.awt.geom.*;
import stdDraw.*;

/**
 * Cette classe décrit le problème du voyageur de commerce. Les variables de
 * classes pose les condition su problème, sous forme d'une liste de villes.
 * Le but du problème est de trouver un itinéraire passant par toutes les
 * villes, avec une distance totale minimale.
 * Chaque instance représente une solution au problème, à savoir un itinéraire.
 * @author simon
 * @version 1.0
 */
public class VoyageurCommerce implements Genome {
	
	/**
	 * Représente une solution au problème : un itinéraire parcourant toutes
	 * les villes
	 */
	private LinkedList<Point2D> permutation;
	
	/**
	 * Nombre de villes à visiter par le voyageur. La complexité du problème
	 * croît selon O(n!).
	 */
	private static int nbVilles=100;
	
	/**
	 * Liste des villes à parcourir
	 */
	private static Point2D [] listeVilles = new Point2D [nbVilles];
	
	private static double tauxMutation = 0.1;
	
	private static Random r = new Random();
	
	/**
	 * Initialise aléatoirement une carte avec les nombre de villes donné en
	 * paramètre de classe
	 */
	public static void initialisation(){
		
		Random r = new Random();
		for (int i=0; i<nbVilles; i++){
			/*
			 * construit une liste de nbVilles points
			 * les coordonnées (x,y) des point sont arbitrairement comprises entre 1 et 10
			 */
			double x = r.nextDouble()*10;
			double y = r.nextDouble()*10;
			listeVilles [i] = new Point2D.Double(x, y);
		}
	}
	
	private double coutPermutation(){
		double cout=0;
		Iterator<Point2D> iter = permutation.iterator();
		if (iter.hasNext()) {
			Point2D v1 = iter.next();
			while (iter.hasNext()) {
				Point2D v2 = iter.next();
				cout += v1.distance(v2);
				v1 = v2;
			}
			//retour à la ville de départ
			cout += v1.distance(permutation.getFirst());
		}
		return cout;
	}
	
	/**
	 * Un permutation de coût élevé est considéré inférieure, puisqu'une
	 * solution optimum au problème doit avoir un coût minimum
	 */
	@Override
	public int compareTo(Genome arg0) {
		VoyageurCommerce arg1 = (VoyageurCommerce)arg0;
		if (this.coutPermutation()==arg1.coutPermutation()){
			return 0;
		} else {
			if (this.coutPermutation()>arg1.coutPermutation()){
				return -1;
			} else {
				return 1;
			}
		}
	}
	
	public void draw() {
		//trace les villes sous forme de points
		StdDraw.setPenColor(StdDraw.BLACK);
		StdDraw.setPenRadius(0.010);
		for (Point2D v : listeVilles) {
			StdDraw.point(v.getX(), v.getY());
		}
		//trace les trajets entre les villes
		StdDraw.setPenColor(StdDraw.RED);
		StdDraw.setPenRadius();
		Iterator<Point2D> iter = permutation.iterator();
		if (iter.hasNext()) {
			Point2D v1 = iter.next();
			while (iter.hasNext()) {
				Point2D v2 = iter.next();
				StdDraw.line(v1.getX(), v1.getY(), v2.getX(), v2.getY());
				v1 = v2;
			}
			StdDraw.line(v1.getX(), v1.getY(), permutation.getFirst().getX(), permutation.getFirst().getY());
		}
		StdDraw.show(10);
	}
	
	@Override
	public void mutation() {
		if (r.nextDouble()<tauxMutation){
			int a, b ;
			a = r.nextInt(nbVilles);
			do {
				b = r.nextInt(nbVilles);
			} while (a==b) ; //a!=b pour muter sur un intervalle
			int debut = Math.min(a, b); //début de l'intervalle muté
			int lg = Math.abs(a-b); //longueur de l'intervalle muté
			for (int i=debut; i<debut+(lg/2); i++) {
				Point2D p = permutation.get(i); // variable intermédiaire
				permutation.set(i,permutation.get(debut+lg-i));
				permutation.set(debut+lg-i,p);
			}
		}
	}

	@Override
	public Genome croisement(Genome parent) {
		VoyageurCommerce vcParent = (VoyageurCommerce) parent;
		int separ = r.nextInt(nbVilles);
		LinkedList<Point2D> newPermutation = new LinkedList<Point2D>();
		for (int i=0; i<separ; i++) {
			newPermutation.addLast(permutation.get(i));
		}
		for (Point2D v : vcParent.permutation){
			if (!newPermutation.contains(v)){
				newPermutation.addLast(v);
			}
		}
		return new VoyageurCommerce(newPermutation);
	}
	
	/**
	 * Créé une solution (un trajet) aléatoire au problème du voyageur de
	 * commerce
	 */
	public VoyageurCommerce() {
		permutation = new LinkedList<Point2D>();
		for (Point2D v : listeVilles) {
			permutation.add(v);
		}
		Collections.shuffle(permutation);
	}
	
	/**
	 * Créé une solution au problème du voyageur de commerce à partir d'une
	 * liste préexistante
	 * @param permutation
	 */
	public VoyageurCommerce(LinkedList<Point2D> permutation) {
		super();
		this.permutation = permutation;
	}

	@Override
	public String toString() {
		return "VoyageurCommerce [ valeur = "+this.coutPermutation()+" ]";
	}
	
	

}
